package com.zwj.interview.动态规划.背包问题;

/**
 * @Author: Zwj
 * @Date: 2022/2/26 18:15
 * <p>
 * 给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。
 * <p>
 * 请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。
 * <p>
 * 假设每一种面额的硬币有无限个。 
 * <p>
 * 输入：amount = 5, coins = [1, 2, 5]
 * 输出：4
 * 解释：有四种方式可以凑成总金额：
 * 5=5
 * 5=2+2+1
 * 5=2+1+1+1
 * 5=1+1+1+1+1
 */
public class 兑换硬币2 {

    /**
     * 转化为背包问题就是：
     * 有一个背包，最大容量为amount，有一系列物品coins，每个物品的重量为coins[i]，每个物品数量无限，问有多少种方法，
     * 能够把背包装满。
     * <p>
     * dp[i][j]表示只是用前i个物品，当背包容量为j时，有dp[i][j]种方法可以装满背包
     */
    public int change(int amount, int[] coins) {
        int n = coins.length;
        int[][] dp = new int[n + 1][amount + 1];
        for (int i = 0; i <= n; i++) {
            //当要凑的金额为0时，那么不需要任何硬币即可
            dp[i][0] = 1;
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= amount; j++) {
                if (j - coins[i - 1] >= 0) {
                    //当使用coins[i-1]这个硬币时，就要剩余的容量
                    //两种结果相加，即为最后结果
                    //到了
                    dp[i][j] = dp[i - 1][j] + dp[i][j - coins[i - 1]];
                } else {
                    //当不使用coins[i-1]这个硬币时，那么就等于之前的结果
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        return dp[n][amount];
    }


    public int change2(int amount, int[] coins) {
        int n = coins.length;
        //dp[x][y]表示使用前x枚硬币，凑出金额为y的方案数
        int[][] dp = new int[n + 1][amount + 1];
        //特殊情况
        for (int i = 0; i <= n; i++) {
            dp[i][0] = 1;
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= amount; j++) {
                //到了dp[i][j]时，有两种情况，一种是前i-1个就已经凑够了，第二种就是前i-1个凑不够
                if (j - coins[i - 1] > 0) {
                    dp[i][j] = dp[i - 1][j] + dp[i][j - coins[i - 1]];
                } else {
                    dp[i][j] = dp[i - 1][j];
                }

            }
        }
        return dp[n][amount];
    }


}